package codetop前三页.第一页;


import jdk.internal.org.objectweb.asm.tree.analysis.Value;
import sun.plugin.javascript.navig.Link;

import java.time.temporal.Temporal;
import java.util.HashMap;

/**总结：
 * lru的考察实质是双向链表+map+伪头尾节点
 * @author ChenweiLin
 * @create 2022-01-05 10:23
 */
public class No3LruCache {

    //双线链表类
    class LinkNode{
        int key;
        int val;
        LinkNode front;//前向指针
        LinkNode next;//后向指针

        public LinkNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }


    class LRUCache {

        int capacity;//cache容量
        HashMap<Integer, LinkNode> map = new HashMap<>();//map的key就是linkNode的key
        //伪头尾节点
        LinkNode head = new LinkNode(0, 0);
        LinkNode tail = new LinkNode(0, 0);

        public LRUCache(int capacity) {
            this.capacity = capacity;
            //初始化的时候头节点和尾节点相连
            head.next = tail;
            tail.front = head;
        }

        public int get(int key) {//get 得到值/不是取出值
            if(map.containsKey(key)){
                LinkNode linkNode = map.get(key);
                moveNodeToTop(linkNode);
                return linkNode.val;
            }else {
                return -1;
            }

        }

        //一、先写put方法
        public void put(int key, int value) {
            if(!map.containsKey(key)){//当双向链表/map没有该点的时候
                if(map.size() == capacity)
                    deleteLastNode();
                //把存放的节点放入队首
                LinkNode linkNode = new LinkNode(key, value);
                LinkNode temp = head.next;
                head.next = linkNode;
                linkNode.front = head;
                linkNode.next = temp;
                temp.front = linkNode;
                map.put(key , linkNode);
            }else{//当双向链表/map有该点的时候,我们需要更新该点至队首
                LinkNode linkNode = map.get(key);
                linkNode.val = value;
                //局部删除+插至队首
                moveNodeToTop(linkNode);
            }
        }

        private void deleteLastNode() {//双向链表和map都要删
            LinkNode lastNode = tail.front;
            map.remove(lastNode.key);//map删除

            //双向链表删除 从尾节点定位
            lastNode.front.next = tail;
            tail.front = lastNode.front;


        }

        private void moveNodeToTop(LinkNode linkNode) {
            LinkNode temp = linkNode.next;
            //局部删除
            linkNode.front.next = temp;
            temp.front = linkNode.front;
            //移至队首
            temp = head.next;
            head.next = linkNode;
            linkNode.front = head;
            linkNode.next = temp;
            temp.front = linkNode;
        }
    }

}
